• 重新調整從 Grind 75 開始，主要還是用 kotlin, 不過因未來會用到 java, python 所以也來複習一下吧。

1.Two Sum

• Array/HashMap, Easy
• introduction
  • 給定整數陣列 nums 和整數目標值 target，請返回兩個索引，使它們的數字和為 target。假設每個輸入只有一組解，且不能使用同一元素兩次。
• solution
  • 用 HashMap 存儲數字與索引，一邊遍歷一邊檢查 target - nums[i] 是否已出現。
  • 時間：O(n)
  • 空間：O(n)
• kotlin

fun twoSum(nums: IntArray, target: Int): IntArray {
    val map = mutableMapOf<Int, Int>()
    for ((i, num) in nums.withIndex()) {
        val complement = target - num
        if (map.containsKey(complement)) {
            return intArrayOf(map[complement]!!, i)
        }
        map[num] = i
    }
    return intArrayOf()
}

• java

public int[] twoSum(int[] nums, int target) {
    Map<Integer, Integer> map = new HashMap<>();
    for (int i = 0; i < nums.length; i++) {
        int complement = target - nums[i];
        if (map.containsKey(complement)) {
            return new int[]{map.get(complement), i};
        }
        map.put(nums[i], i);
    }
    return new int[0];
}

• python

def twoSum(nums, target):
    num_map = {}
    for i, num in enumerate(nums):
        if target - num in num_map:
            return [num_map[target - num], i]
        num_map[num] = i

• follow up

  • 如果要找三數之和（3Sum）怎麼改？
    • solution
      • 目標是找到所有 nums[i] + nums[j] + nums[k] = 0（或指定 target）的三元組。
      • 標準做法：先排序陣列，固定第一個數，再用雙指針找後兩個數。
      • 時間：O(n²)
      • 空間：O(1)（排序除外）

  fun threeSum(nums: IntArray): List<List<Int>> {
    nums.sort()
    val res = mutableListOf<List<Int>>()
    for (i in nums.indices) {
        if (i > 0 && nums[i] == nums[i - 1]) continue
        var l = i + 1
        var r = nums.size - 1
        while (l < r) {
            val sum = nums[i] + nums[l] + nums[r]
            when {
                sum < 0 -> l++
                sum > 0 -> r--
                else -> {
                    res.add(listOf(nums[i], nums[l], nums[r]))
                    l++
                    r--
                    while (l < r && nums[l] == nums[l - 1]) l++
                    while (l < r && nums[r] == nums[r + 1]) r--
                }
            }
        }
    }
    return res
  }
  

  • 如果陣列已經排序，怎麼用雙指針解法？
    • solution
      • 如果 nums 已排序，可以用左右指針從頭尾夾逼。
      • 若 sum < target → 左指針右移
      • 若 sum > target → 右指針左移
      • 時間：O(n)
      • 空間：O(1)

  fun twoSumSorted(nums: IntArray, target: Int): IntArray {
    var l = 0
    var r = nums.size - 1
    while (l < r) {
        val sum = nums[l] + nums[r]
        when {
            sum == target -> return intArrayOf(l, r)
            sum < target -> l++
            else -> r--
        }
    }
    return intArrayOf()
  }
  

  • 如果輸入很大，如何降低空間複雜度？
    • 原本 HashMap 解法是 O(n) 空間。
    • 若陣列已排序 → 使用 雙指針，O(1) 空間。
    • 若未排序但空間受限 → 可先排序再雙指針，O(1) 空間但 O(n log n) 時間。
    • 若不能改變原陣列 → 可複製一份排序（O(n) 空間），或用外部排序法處理。